home *** CD-ROM | disk | FTP | other *** search
/ NeXT Education Software Sampler 1992 Fall / NeXT Education Software Sampler 1992 Fall.iso / Programming / Source / 2DLab / cheap.m < prev    next >
Encoding:
Text File  |  1992-01-14  |  7.7 KB  |  259 lines
  1.  
  2. #include <stdlib.h>
  3. #ifdef MYDIR
  4. #else
  5. #include "TwoDView.h"
  6. #include "TwoDTSP.h"
  7. #include <appkit/graphics.h>
  8. #endif
  9. #include <math.h>
  10. #include <limits.h>
  11. #include <stdio.h>
  12. #include "tspheaders.h"
  13. #include "prototypes.h"
  14. /************************************************************************/
  15. /* This function implements the Cheapest Insertion Algorithm for the
  16.    Travelling Salesperson Algorithm.  It provides an approximate optimal
  17.    value rather than the optimal value. 
  18.  
  19.    Reference: Salkin & Mathur, Foundations Of Integer Programming, 1989
  20.               North-Holland, p 683.
  21. */
  22. /************************************************************************/
  23. /* Parameters:   TwoDView *self: Ye Old Drawing Object
  24.  
  25.                     float *Data: Pointer to the list of points.
  26.                                  Used to draw intermediate graph.
  27.  
  28.                 float *Distance: Pointer to area that contains the
  29.                                  Distances Between Each Pair of Cities
  30.  
  31.                       int *Tour: Pointer to area that will contain the
  32.                                  indices of the n arcs that are selected 
  33.                                  to be a part of the tour
  34.  
  35.              int NumberOfCities: Number of cities in the problem
  36. */
  37. /************************************************************************/
  38. /************************************************************************/
  39. #ifdef MYDIR
  40. float CheapestInsertion(float *Distance,int *Tour,int NumberOfCities) {
  41. #else
  42. float CheapestInsertion(TwoDView *self,float *data,float *Distance,int *Tour,
  43.                         int NumberOfCities) {
  44. #endif
  45. int i,j,k,l,m,x,y,I,J,Arc,From,To,CurrentCity,SubTourEnd,NewCity,FromIndex;
  46. int *OnTour;
  47. float MinDistance,OldDistance,ThisDistance,NewDistance,OptimalValue;
  48. char msg[256];
  49.  
  50. /* allocate space for OnTour */
  51. OnTour = (int *)malloc(NumberOfCities*sizeof(int));
  52. if (OnTour == (int *) 0)
  53.   printf("Malloc for OnTour failed. \n");
  54.  for (i=0;i<NumberOfCities;i++) {
  55.    OnTour[i] = 0;
  56.  }
  57.  
  58. #ifdef DEBUGMYDIR
  59.  for (i=0;i<(NumberOfCities-1)*NumberOfCities/2;i++) {
  60.    printf("Distance[%d] = %f; \n",i,Distance[i]);
  61.  }
  62.  #endif
  63.  
  64.  /* find the two cities with the minimum distance */
  65.  /* these two cities make up the initial subtour  */
  66.  MinDistance = ClosestCities(Distance,&From,&To,NumberOfCities);
  67.  
  68.  /* if MinDistance doesn't change, there is a problem ... */
  69.  if (MinDistance == INT_MAX) {
  70.    printf("Error no initial subtour found. \n");
  71.  #ifdef DEBUGMYDIR 
  72.  #else
  73.    STATUS("No initial subtour found.");
  74.  #endif
  75.  }
  76.  #ifdef DEBUGMYDIR
  77.  else {
  78.    printf("initial subtour \n");
  79.    printf("from %d to %d distance %f \n",From,To,MinDistance);
  80.  }
  81.  #endif
  82.  
  83.  /* given a subtour of m cities, add city k with minimum insertion cost */
  84.  /* cost of inserting city k between cities i and j =
  85.               Distance(i,k) + Distance(k,j) - Distance(i,j) */
  86.  
  87.  /* OnTour indicates status of city 
  88.     1 -- city is on tour 0 -- city is not yet on the tour */
  89.  Tour[0] = Tour[3] = From;
  90.  Tour[1] = Tour[2] = To;
  91.  OnTour[From] = OnTour[To] = 1;
  92.  
  93.  /* FromIndex is the number of the city currently being tested */
  94.  FromIndex = 0;
  95.  NewDistance = INT_MAX; 
  96.  
  97.  OptimalValue = 2*MinDistance;
  98.  SubTourEnd = 1;
  99.  CurrentCity = -1;
  100.  NewCity = NumberOfCities;
  101.  
  102.  /* keep adding cities until you include all NumberOfCities of them */
  103.  while (SubTourEnd < NumberOfCities-1) {
  104.  
  105.  #ifdef DEBUGMYDIR
  106.    printf("Start of Iteration with %d cities in tour \n",SubTourEnd+1);
  107.    printf("From is %d \n",From);
  108.    printf("To is %d \n",To);
  109.    printf("FromIndex is %d \n",FromIndex);
  110.  #else
  111.    sprintf(msg,"From %d To %d",From, To); //added wgr
  112.    STATUS(msg);// wgr
  113.  #endif
  114.  
  115.    /* at the end of this while loop, there will be a new city to insert */
  116.    while (CurrentCity < SubTourEnd) {
  117.      /* look at the next city already on the tour */
  118.      CurrentCity+=1;
  119.      From = Tour[2*CurrentCity];
  120.      To = Tour[2*CurrentCity+1];
  121.      OldDistance = Distance[kfrom(From,To,NumberOfCities)];
  122.  
  123.      /* look at all arcs starting at From */
  124.      I = ArcIndex(From,NumberOfCities);
  125.      J = ArcIndex((From+1),NumberOfCities);
  126.      for (Arc=I;Arc<J;Arc++) {
  127.        /* j = terminating end of this arc */
  128.        j = Arc-I+From+1;
  129.        /* if the city at the other end isn't already on the tour ...*/
  130.        if (!OnTour[j]) {
  131.      /* Is the arc a new candidate for insertion? */
  132.      if ((j != From) && (j != To)) {  
  133.        k = kfrom(From,j,NumberOfCities);
  134.        l = kfrom(j,To,NumberOfCities);
  135.        ThisDistance = Distance[k] + Distance[l] - OldDistance;
  136.        if (ThisDistance < 0) {
  137.          printf("Error: ThisDistance = %f for From %f To %f j %f \n",
  138.              From,To,j);
  139.        }
  140.        if (ThisDistance < NewDistance) {
  141.  #ifdef DEBUGMYDIR
  142.          printf("Changing cities from %d to %d \n",NewCity,j);   
  143.          printf("From, To, j, %d %d %d \n",From,To,j);
  144.  #else
  145.          sprintf(msg,"Change from %d to %d",From,To);
  146.          STATUS(msg);
  147.  #endif
  148.          NewDistance = ThisDistance;
  149.          NewCity = j;
  150.          FromIndex = CurrentCity;
  151.        } 
  152.      } 
  153.        }
  154.      }
  155.  
  156.      /* look at all arcs ending at From */
  157.      for (m=0;m<From;m++) {
  158.        /* if the starting city isn't already on the tour ...*/
  159.        if (!OnTour[m]) {
  160.      /* Is this arc a new candidate for insertion? */
  161.      if ((m != From) && (m != To)) {  
  162.        k = kfrom(m,From,NumberOfCities);
  163.        l = kfrom(m,To,NumberOfCities);
  164.        ThisDistance = Distance[k] + Distance[l] - OldDistance;
  165.        if (ThisDistance < 0) {
  166.          printf("Error: ThisDistance = %f for From %f To %f m %f \n",
  167.              From,To,m);
  168.        }
  169.        if (ThisDistance < NewDistance) {
  170.  #ifdef DEBUGMYDIR
  171.          printf("Changing cities from %d to %d \n",NewCity,m);   
  172.          printf("From, To, J, %d %d %d \n",From,To,m);
  173.  #else
  174.          sprintf(msg,"change from %d to %d",NewCity,m);
  175.          STATUS(msg);
  176.  #endif
  177.          NewDistance = ThisDistance;
  178.          NewCity = m;
  179.          FromIndex = CurrentCity;
  180.        } 
  181.      } 
  182.        }
  183.      }
  184.    }
  185.  
  186.    if (NewCity >= NumberOfCities) {
  187.      printf("Error: new city has not been found for tour. \n");
  188.      CurrentCity = SubTourEnd = NumberOfCities;
  189.      OptimalValue = -1;
  190.    }
  191.    else {
  192.      /* add the new arc going from j to FromIndex+1 Tour */
  193.  #ifdef DEBUGMYDIR
  194.      printf("adding arc from %d to %d \n",NewCity,Tour[2*FromIndex+1]);
  195.  #else
  196.      sprintf(msg,"add arc %d to %d \n",NewCity,Tour[2*FromIndex+1]);
  197.      STATUS(msg);
  198.  #endif
  199.      SubTourEnd+=1;
  200.      Tour[2*SubTourEnd] = NewCity;
  201.      Tour[2*SubTourEnd+1] = Tour[2*FromIndex+1];
  202.      OnTour[NewCity] = 1;
  203.  
  204.      /* replace arc indexed by FromIndex in Tour with new arc going from
  205.     old From to NewCity */
  206.  #ifdef DEBUGMYDIR
  207.      printf("replacing arc from %d to %d with %d to %d \n",
  208.        Tour[2*FromIndex],Tour[2*FromIndex+1],Tour[2*FromIndex],NewCity);
  209.  #else
  210.      sprintf(msg,"replace %d %d with %d %d",
  211.                 Tour[2*FromIndex],Tour[2*FromIndex+1],Tour[2*FromIndex],NewCity);
  212.      STATUS(msg);
  213.  #endif
  214.      Tour[2*FromIndex] = Tour[2*FromIndex];
  215.      Tour[2*FromIndex+1] = NewCity;
  216.  
  217.      /* update the Optimal Value */  
  218.      OptimalValue+=NewDistance;
  219.  #ifdef DEBUGMYDIR
  220.      printf("addding %f to Opval to get %f \n",NewDistance,OptimalValue);
  221.  #endif
  222.  
  223.      /* get ready to start at the top of the list again */
  224.      FromIndex = 0;
  225.      CurrentCity = -1;
  226.      NewDistance = INT_MAX; 
  227.      NewCity = NumberOfCities; 
  228.  
  229.  #ifdef DEBUGMYDIR
  230.      /* print out current subtour */
  231.      for (i=0;i<2*(SubTourEnd+1);i++) {
  232.          printf("i tour %d %d \n",i,Tour[i]);
  233.      }
  234.  #endif
  235.  #ifdef MYDIR
  236.  #else
  237.      /* draw the intermediate tour */
  238.      PSnewinstance();
  239.     for(i=0;i<2*(SubTourEnd+1);i+=2) { 
  240.      x = Tour[i];
  241.      y = Tour[i+1];
  242.      [self drawEdge:X(x):Y(x):X(y):Y(y)];
  243.     }
  244.      NXPing();
  245.      [self->optimalValueField setFloatValue: OptimalValue at: 0];
  246.      usleep(self->drawTime);
  247. #endif
  248.     
  249. }
  250. }
  251.  
  252. /* clean up */
  253. free(OnTour);
  254.  
  255. /* return the optimal value */
  256. return(OptimalValue);
  257. }
  258.         
  259.